package com.example.leetcode.twopoint.common;

import com.example.leetcode.array.common.ArrayUtils;
import com.example.leetcode.linkedlist.common.ListNode;

import java.util.*;

public class TwoPointUtils {
    public static int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return 1;
        }
        int left = 0;
        int right = 1;
        while (right < nums.length) {
            if (nums[right] == nums[left]) {
                right++;
            } else {
                left++;
                nums[left] = nums[right];
            }
        }
        // 返回新数组的长度
        return left + 1;
    }

    public static ListNode removeNthFromEnd(ListNode head, int n) {
        if (n <= 0) {
            return head;
        }
        ListNode rightNode = new ListNode(-1, head);
        ListNode leftNode = new ListNode(-1, head);

        for (int i = 1; i <= n; i++) {
            if (rightNode.next == null) {
                return head;
            }
            rightNode = rightNode.next;
        }
        // 删除的是第一个结点
        if (rightNode.next == null) {
            return head.next;
        }
        // 删除的不是第一个结点
        while (rightNode.next != null) {
            rightNode = rightNode.next;
            leftNode = leftNode.next;
        }
        leftNode.next = leftNode.next.next;
        return head;
    }

    public static int removeElement(int[] nums, int val) {
        int left = 0;
        int right = 0;
        while (right < nums.length) {
            if (nums[right] != val) {
                if (left != right) {
                    nums[left] = nums[right];
                }
                right++;
                left++;
            } else {
                right++;
            }
        }
        return left;
    }

    public static int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int result = 0;
        while (left < right) {
            result = Math.max(result, (right - left) * Math.min(height[left], height[right]));
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return result;
    }

    public static boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode left = head;
        ListNode right = head;
        while (true) {
            if (left.next == null) {
                return false;
            } else {
                left = left.next;
            }
            if (right.next == null || right.next.next == null) {
                return false;
            } else {
                right = right.next.next;
            }
            if (right == left) {
                return true;
            }
        }
    }

    public static void moveZeroes(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
        int left = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                if (i != left) {
                    nums[left] = nums[i];
                }
                left++;
            }
        }
        for (int i = left; i < nums.length; i++) {
            nums[i] = 0;
        }
    }


    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums.length == 3) {
            if (Arrays.stream(nums).sum() == 0) {
                result.add(ArrayUtils.intArrayToList(nums));
            }
            return result;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            twoSum(nums, i, result);
        }
        return result;
    }

    private static void twoSum(int[] nums, int index, List<List<Integer>> result) {
        int left = index + 1;
        int right = nums.length - 1;
        while (left < right) {
            int sum = nums[index] + nums[left] + nums[right];
            if (sum == 0) {
                List<Integer> list = new ArrayList<>();
                list.add(nums[index]);
                list.add(nums[left]);
                list.add(nums[right]);
                result.add(list);
                while (left < right && nums[left + 1] == nums[left]) {
                    left++;
                }
                while (left < right && nums[right - 1] == nums[right]) {
                    right--;
                }
                left++;
                right--;
            } else if (sum > 0) {
                right--;
            } else {
                left++;
            }
        }
    }

    public static int removeDuplicatesPro(int[] nums) {
        if (nums.length < 3) {
            return nums.length;
        }
        int left = 2;
        int right = 2;
        while (right < nums.length) {
            if (nums[right] == nums[left - 1] && nums[right] == nums[left - 2]) {
                right++;
            } else {
                nums[left] = nums[right];
                left++;
                right++;
            }
        }
        return left;
    }

    public static void reverseString(char[] s) {
        int left = 0;
        int right = s.length - 1;
        while (left < right) {
            char c = s[left];
            s[left] = s[right];
            s[right] = c;
            left++;
            right--;
        }
    }

    public static String reverseVowels(String s) {
        if (s.length() <= 1) {
            return s;
        }
        char[] vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};
        char[] array = s.toCharArray();
        Set<Character> set = new HashSet<>();
        for (char vowel : vowels) {
            set.add(vowel);
        }
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            while (left < right && !set.contains(s.charAt(left))) {
                left++;
            }
            while (left < right && !set.contains(s.charAt(right))) {
                right--;
            }
            char temp = array[left];
            array[left] = array[right];
            array[right] = temp;
            left++;
            right--;
        }
        return String.valueOf(array);
    }

    public static int[] sortArrayByParity(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            while (left < right && nums[left] % 2 == 0) {
                left++;
            }
            while (left < right && nums[right] % 2 != 0) {
                right--;
            }
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
        }
        return nums;
    }

    public static int getCommon(int[] nums1, int[] nums2) {
        int p1 = 0;
        int p2 = 0;
        while (p1 < nums1.length && p2 < nums2.length) {
            if (nums1[p1] == nums2[p2]) {
                return nums1[p1];
            } else if (nums1[p1] < nums2[p2]) {
                p1++;
            } else {
                p2++;
            }
        }
        return -1;
    }

    public static boolean isStrobogrammatic(String num) {
        Map<Character, Character> map = new HashMap<>();
        map.put('6', '9');
        map.put('0', '0');
        map.put('1', '1');
        map.put('8', '8');
        map.put('9', '6');
        char[] array = num.toCharArray();
        int left = 0;
        int right = array.length - 1;
        while (left <= right) {
            if (left == right && array[left] != '0' && array[left] != '1' && array[left] != '8') {
                return false;
            }
            if (map.get(array[left]) == null || map.get(array[left]) != array[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public static int[] twoSumII(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                int[] result = {left + 1, right + 1};
                return result;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[]{-1, -1};
    }


    private static double getMidian(int[] nums) {
        if (nums.length % 2 == 0) {
            return (nums[nums.length / 2 - 1] + nums[nums.length / 2]) * 1.0 / 2;
        } else {
            return nums[nums.length / 2];
        }
    }

    public static String longestPalindrome(String s) {
        String result = "";
        for (int i = 0; i < s.length(); i++) {
            // 单字符中心型
            String res1 = getPalindrome(i, i, s);
            String res2 = "";
            if (i + 1 < s.length() && s.charAt(i) == s.charAt(i + 1)) {
                // 双字符中心型
                res2 = getPalindrome(i, i + 1, s);
            }
            if (result.length() < res1.length()) {
                result = res1;
            }
            if (result.length() < res2.length()) {
                result = res2;
            }
        }
        return result;
    }

    private static String getPalindrome(int left, int right, String s) {
        while (left >= 0 && right <= s.length() - 1 && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return s.substring(left + 1, right);
    }

    public static List<Boolean> camelMatch(String[] queries, String pattern) {
        List<Boolean> ans = new ArrayList<>(queries.length);
        char[] patternArray = pattern.toCharArray();
        for (String query : queries) {
            char[] charArray = query.toCharArray();
            int patternIndex = 0;
            int j = 0;
            int bigCount = 0;
            int patternBigCount = 0;
            for (; j < charArray.length; j++) {
                if (charArray[j] >= 'A' && charArray[j] <= 'Z') {
                    bigCount++;
                }
                if (patternIndex >= pattern.length()) {
                    if (charArray[j] >= 'A' && charArray[j] <= 'Z') {
                        break;
                    }
                    continue;
                }
                if (charArray[j] == patternArray[patternIndex]) {
                    if (patternArray[patternIndex] >= 'A' && patternArray[patternIndex] <= 'Z') {
                        patternBigCount++;
                    }
                    patternIndex++;
                }
            }
            if (j == charArray.length && patternIndex == patternArray.length && bigCount == patternBigCount) {
                ans.add(true);
            } else {
                ans.add(false);
            }
        }
        return ans;
    }

    public static void sortColors(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        int cur = 0;

        while (cur <= right) {
            if (nums[cur] == 0) {
                swap(nums, cur, left);
                left++;
                cur++;
            } else if (nums[cur] == 2) {
                swap(nums, cur, right);
                right--;
            } else {
                cur++;
            }
        }
    }

    public static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
